
\documentclass[11pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath}
\usepackage{amsfonts,amssymb}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\newcommand{\myparagraph}[1]{\paragraph{#1}\mbox{}\\}
\newcommand{\eps}{\epsilon}

\begin{document}

\input{preamble.tex}

\lecture{3}{Aug 28, 2012}{Elena Grigorescu}{Purnima Kapoor}


\section{Intro}

In the previous lectures we introduced various sublinear models of computation and we talked about some basic probabilistic tools for analyzing the performance of randomized algorithms.
We then showed two applications of Chernoff's bound. We saw how to quickly estimate the fraction of $1$'s in a binary string, and then we saw how to reduce the error of a randomized algorithm that makes a yes/no decision, say from  $49\%$ to $1\%$. More generally, if such an algorithm outputs incorrect answers with probability $1/3$ then by running it $\log \frac{1}{\delta}$ times and outputting the majority answer, the error probability can be reduced  to $\delta>0$.


In this lecture we will revisit the Property testing model, which will be the focus of a few future lectures as well. We will then show a property testing algorithm for the problem of testing connectivity in sparse graphs.

 


\section{The Property Testing model} 

The Property testing model is a randomized model of computation that relaxes the usual decision model. While in the classical decision model an algorithm  distinguishes between inputs having a property and inputs not having the property, in the Property Testing model an algorithm is required to only distinguish between inputs having the property and inputs that are very far from having the property. That is, for the remaining inputs (inputs that are close to having the property), the algorithm can output an arbitrary answer.


What do we gain from this relaxation? It turns out that many hard decision problems (say for problems that are NP complete, eg. 3-colorability) one can obtain very efficient (sublinear time, or even constant time) property testing algorithms. Sublinear time PT algorithms are also interesting even for problems for which their classical decision version can be solved in polynomial time. In practice, such algorithms are useful when dealing with massive data sets (say, internet data, social data, biological data) and when dealing with data that changes at a rapid rate. In fact we're running property testing algorithms in our daily lives; for example, if you would be offered a few sample chocolate bytes from a chocolate store it could help you quickly decide whether you'd want to enter the store (if their brand seems great) or stay away from it (if their brand seems very bad). 


We'll next start formalizing the model.

We will denote by a {\em property} ${\cal P}$ the collection of objects that share a certain property. For example, 

\begin{enumerate}
\item ${\cal P}=\{\mbox{graphs that can be colored with 3-colors}\}$
\item ${\cal P}=\{\mbox{bipartite graphs}\}$
\item ${\cal P}=\{\mbox{linear functions} f: Z_2^n\rightarrow Z_2 \}$
\item ${\cal P}=\{\mbox{uniform distribution over domain $D$.}\}$
\item ${\cal P}=\{f:D\rightarrow \{0,1\}, f(x)=1\}.$
\end{enumerate}


\paragraph{Input access} A PT algorithm for a property ${\cal P}$ is given oracle/black-box access to its input. If the input is represented as a function $f:D\rightarrow R$, then the algorithm $A$ tosses some random coins based on which it picks a query $i\in D$ and receives back $f(i)$ from the oracle for $f$. Based on the answers to a few queries, $A$ should output a yes/no verdict, that represents its decision that distinguishes between the input $f$ having the property ${\cal P}$ or being far from having it.  
If the input is represented as a graph $G=G(V, E)$ with vertex set $V$ and edge set $E$, then a query is a pair $(v, u)\in V\times V$ and the answer to this query is $1$ if there is an edge between $u$ and $v$ in $E$, and $0$ otherwise.

\paragraph{Notions of distance}
What does it mean to be far/close to a property?
The most common notion of distance over discrete domains is the Hamming distance.  The relative Hamming distance between functions $f, g:D\rightarrow R$ is $\delta_H(f,g) = \frac{|\{ x:f(x) \ne g(x)  \} |} {|D|}.$
The relative distance between $f$ and a property ${\cal P}$ is 
$\delta_H(f, {\cal P})=\min_{g\in {\cal P}} \delta_H(f, g)$.

For two graphs $G_1$, $G_2$ on $n$ vertices, a typical notion of distance is given by the number of edges that need to be added/removed to/from $G_1$ in order to obtain $G_2$. The relative distance between two graphs is computed with respect to an upper bound on the number of edges in the graphs, and it depends on the graph representation model (ie. adjacency matrix model (for dense graphs) or adjacency list model (for sparse graphs)).

We say that $f$ is $\eps$-far from ${\cal P}$ if $\delta_H(f, {\cal P})>\eps$. Otherwise $f$ is $\eps$-close to ${\cal P}$.
A graph on $n$ vertices in the dense graph model is $\eps$-far from a graph property $\cal P$ if it needs to be modified in $\eps \binom{n}{2}$ many edges in order to obtain a graph in ${\cal P}$. A graph on $n$ vertices and of bounded degree $d$ (in the sparse graph model) is $\eps$-far from a property $\cal P$ if it needs to be modified in $\eps n d$ many edges in order to obtain a graph from ${\cal P}$.


We can now formalize the PT model.

\begin{definition} \label{k-locally}
A property $P_n\subset \{h: D \rightarrow R\}$ (where $D$ and $R$ are the finite domain and range, and $|D|=n$) is called \emph{$k$-locally testable}  if there exists a randomized algorithm $A$ such that
 \begin{enumerate}
 \item on input $\eps>0$ and $f:D\rightarrow R$ that $A$ can access via queries
  \item $A$ makes $k=k(\eps, n)$ queries $q_1, q_2, \ldots , q_k$ to $f$ 
  \item based on the answers it receives (namely the values $f(q_1), f(q_2), \ldots , f(q_k)$) $A$ will output as follows:
\begin{enumerate}
\item (Correctness:) If $f \in P_n$, then $A$ says yes with probability $\frac{2}{3}$;
 \item (Soundness:) If $f$ is $\eps$-far from $P_n$ then $A$ says no with probability $\frac{2}{3}$.
\end{enumerate}
\end{enumerate}
\end{definition}


The main parameter of the algorithm is its query complexity $k=k(\eps, n)$, which is often a measure of the running time of the algorithm. The goal is to obtain algorithms of query complexity $k<<n$. We will see a few PT algorithms of query complexity independent of $n$, namely $k=k(\eps)$.

A PT algorithm is single-sided if it always accepts inputs in ${\cal P}$. Otherwise it is 2-sided.

In the first lecture we saw a very simple example of a single-sided PT algorithm running in time $\frac{2}{\eps}$ that was a tester for the property ${\cal P}=\{f:[n]\rightarrow \{0,1\}, f(i)=1\}$. As a quick reminder, the way the algorithm operated was by picking a random sample  of $\frac{2}{\eps}$ many elements $i\in D$ and rejecting if for any such $i$, $f(i)=0$. If so, then it would have found a witness to $f$ not satisfying the property and rejected the input. Otherwise, if all the queries returned the value $1$ then the algorithm accepted its input $f$.


We emphasize here that usually, when building a one-sided error PT algorithm, we look for small violating patterns in the input (i.e. witnesses to not having the property). If such patterns are found we reject. A typical test $A$ usually looks as follows: on input $\eps$, $f$, repeat $s$ times a basic subroutine $A'$ and only accept if $A'$ has never rejected. For example, in the test above the basic subroutine was: pick a random $i\in [n]$ and reject if $f(i)=0$.  What should $s$ be?  The value of $s$ can be computed from analyzing the probability of finding a witness in the basic test. We saw in the analysis of the test above from the 1st lecture that if the basic test catches a witness with probability $p$, then repeating it $s=2/p$ times increases the probability of catching a witness to $2/3$.  We will use this observation again and again in the analysis of future property testing algorithms.

In the remainder of the lecture we show the first example of a non-trivial PT algorithm, namely for the problem of testing connectivity of graphs.

\section{Testing graph connectivity}


Earlier in the lecture we mentioned about the fact that the distance between graphs depends on the representation model. If $G$ and $H$ are dense graphs (i.e. graphs with $\alpha n^2$ edges where $\alpha>0$, then 

$$\delta(G, H)=\frac{1}{\binom{n}{2}}\cdot({\#\mbox{ edges that need to be modified in order to get from }G \mbox{ to } H}).$$ On the other hand, if $G$ and $H$ are sparse graphs, i.e. in the adjacency list model where $M$ is a bound on the number of edges in the graphs, then $$\delta(G, H)=\frac{1}{M}\cdot({\#\mbox{ edges that need to be modified in order to get from }G \mbox{ to } H}).$$
  

Let ${\cal P}=\{\mbox{graphs that are connected}\}$. Suppose that we work in the adjacency matrix model. What would be a PT algorithm for testing ${\cal P}$? First, let us understand what being far from ${\cal P}$ means. By definition a graph that is $\eps$-far from ${\cal P}$ should need to be modified in $\eps \binom{n}{2}$ places in order to become connected. But notice that one can easily make any $n$-vertex graph into a connected graph by only adding $n-1$ edges, i.e. assymptotically much fewer than $\eps \binom{n}{2}$. So any graph in the dense graph model is $\eps$ close to being connected, and hence the trivial test that always accepts is a test for connectivity.


Things become more interesting though if we focus on graphs where the number of edges is linear in $n$, for example in the bounded degree graph model where a bound $nd$ on the number of edges is known.

In what follows we show a variant of a test for connectivity that can be modified to work in the bounded degree model. 
 We show how to test the property ${\cal P}$ defined above (i.e. the set of connected graphs) under the following notion of distance.

\begin{definition}
Graph $G$ is $\eps$-far from ${\cal P}$ if we need to add $\eps nd$ edges to $G$ in order to obtain a graph in ${\cal P}$(i.e. a connected graph).
\end{definition}


The test and its analysis exemplify the basic ideas that are also used in testing connectivity in the bounded degree list model, where in order to maintain the degree bound one is allowed to both add and delete edges from the graph. For a treatment of this model we refer to \cite{GR02}.

\begin{theorem}\label{connectivity}
${\cal P}$ is testable with one-sided error by a test that makes $O(\frac{1}{(\eps d)^3})$ queries.
\end{theorem}

Notice that the query complexity is a constant, independent of the size of the input graph. Also, we are looking for a one sided error test, namely a test that will always accept connected graphs. And we want to reject graphs that are far from being connected. What do graphs that are far from being connected look like?

The next lemma tells us about the structure of such graphs.


\begin{lemma}\label{lem:comp1}
If $G$ is $\eps$-far from being connected then $G$ has at least $\eps  dn+1$ connected components.
\end{lemma}
\begin{proof}
Suppose $G$ has fewer than $\eps dn +1$ connected components. Then one can connect all of them by adding $\eps dn-1$ edges, which contradicts the fact that $G$ is $\eps$-far from ${\cal P}$.

\end{proof}

\begin{lemma}\label{lem:smallcomp}
If $G$ is $\eps$-far from being connected then it has  $>\frac{\eps}{2} dn$ connected components of size $<\frac{2}{\eps d}$.
\end{lemma}

\begin{proof}
We show that $G$ has $\leq\frac{\eps}{2} dn$ components of size $\geq \frac{2}{\eps d}$. Indeed, otherwise $G$ would have $> \frac{\eps}{2} dn$ components of size $\geq \frac{2}{\eps d}$ and so it would have more than $n$ vertices, a contradiction. By Lemma \ref{lem:comp1} it follows that $G$ had $\geq \eps dn+1-\frac{\eps}{2} dn=\frac{\eps}{2} dn+1$ connected components of size $<\frac{2}{\eps d}$.  

\end{proof}


So we have shown that graphs that are $\eps$-far from being connected have many small connected components (i.e. of size $<\frac{2}{\eps d}$.) 
This structural property that describes the local structure of graphs that are far from being connected should help us design a test for connectivity.
The small connected components will be witnesses to the fact that the input is not connected.

We are now ready to describe our test for connectivity.


\begin{algorithm}
\caption{Property testing algorithm for connectivity}\label{alg:connect}
\begin{algorithmic}
\State Input: $\eps>0$, $G$ on $n$ nodes
\State Pick $s=\frac{4}{\eps d}$ vertices $v_1, v_2, \ldots, v_s$
\State For each $v_i$ run a Breath First Search (BFS) until we reached $\frac{2}{\eps d}$ nodes, or we discovered a connected component of size $<\frac{2}{\eps d}$. In the latter case output {\bf reject}
\State If no small connected component was found at the end of the previous  step then output {\bf accept.}
\end{algorithmic}
\end{algorithm}


\begin{proof}[of Theorem~\ref{connectivity}]

{\bf Query analysis} 
The number of queries that Algorithm~\ref{alg:connect} makes is the same as the number of edges it sees. There are at most $(\frac{2}{\eps d})^2$ edges queried in each BFS search, so the query complexity of the test is $\frac{4}{\eps d} \cdot \frac{4}{(\eps d)^2}=O({1}/{(\eps d)^3})$ queries  (so a number independent of the size of the graph $G$).
 
 
 Let us now verify that Algorithm~\ref{alg:connect} is a one-sided error PT algorithm for ${\cal P}$.

{\bf Correctness:} Suppose $G \in {\cal P}$. Then clearly $G$ is always accepted.

{\bf Soundness:} Suppose $G$ is $\eps$-far from ${\cal P}$.
Then by Lemma~\ref{lem:smallcomp} it must have at least  $>\frac{\eps}{2} dn$ connected components of size $<\frac{2}{\eps d}$ (call such a component {\em small}). Since each such component has at least one vertex it follows that if we uniformly picked a random vertex $v\in V$ 
\[
p=\Pr[v \in \mbox{ small component}]\geq \frac{\eps}{2n} dn
=\frac{\eps}{2} d.
\]

Therefore,

\begin{eqnarray*}
\Pr[\mbox{test accepts}]&=\Pr[\mbox{none of the} s \mbox{ vertices picked landed in a small component}]\\
&<(1-p)^{2/p}\leq e^{-2}<1/3.
\end{eqnarray*}

Observe again that the `basic test' for connectivity is to pick a uniformly random vertex, run BFS and see if it belongs to a small connected component in which case reject. As we have seen above this test catches a small connected component (witness) with probability $p$ and therefore, in order to improve the test's chance of catching a witness we repeated the basic test $s=2/p$ many times.

\end{proof}


We remark that a tighter analysis leads to a test of query complexity $O(\frac{1}{\eps^2}\log^2(\frac{1}{\eps d}))$ for ${\cal P}$ (in the unbounded degree setting) and of query complexity $O(\frac{1}{\eps}\log^2(\frac{1}{\eps d}))$ for in the bounded degree setting where $d$ is a bound on the degrees of vertices in $G$ (See \cite{GR02}).
  
\bibliographystyle{plain}
\bibliography{biblio}

\end{document}


